package com.linwen.excise.niuke._80;

import java.util.Scanner;

/**
 * @author wlw
 * @date 2023/3/17 11:08 PM
 *
 * 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
 * 注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。
 */
public class _61放苹果 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        System.out.println(count(m,n));
    }
    // 计算放苹果方法的数目

    /**
     * m个苹果放进n个盘子，求不同放法的种数，可以分为两类情况：
     * 1.让每个盘子都有苹果放着。
     * 2.至少有一个盘子空着。
     * 有且仅有这两种情况，两种情况没有交集。
     * 7个苹果放进3个盘子，共有8种不同放法，可以用此实例加深以上理解。
     * 现在，用f(m,n)表示将m个苹果放进n个盘子不同放法的种数。
     * 第一种情况相当于给每个盘子先发1个苹果，再将m-n个苹果放进n个盘子里，不同放法种数为f(m-n,n)。
     * 第二种情况相当于摒弃掉空着的那个盘子，将m个苹果放进n-1个盘子里，不同放法种数为f(m,n-1)。因此，f(m,n) = f(m-n,n)+f(m,n-1)。
     * 至此，问题规模已经减小了，再结合递归出口，就可以完成求解了。
     * */
    private static  int count(int m, int n) {
        // 没有苹果或者只剩一个盘子
        if (m == 0 || n == 1) return 1;
        // 盘子大于苹果， 则不考虑多出来的盘子
        if (n > m) return count(m, m);
        return count(m, n-1) + count(m - n, n);
    }
}
